註：本文同步刊載在Medium，若習慣Medium的話亦可去那邊看呦！

昨天的題目，請參見下面的解法：
https://ithelp.ithome.com.tw/articles/10213277

接下來我們要來談談一個也算是蠻重要的資料結構：
堆積(heap)，以及在Python中對應的模組heapq。

什麼是heap呢?
Heap是一種特別的完全二元樹。
這時候讀者又會問了：
那什麼是完全二元樹？
簡單來說，就是一棵二元樹直到最後一層之前，
由左往右都是填滿節點的狀態，中途沒有空缺，
唯有最後一層的右側會缺節點而已。

那麼，heap是怎麼個特別法呢？
當取一棵完全二元樹中的任何一個節點，
對應父(母)節點的值永遠小於等於子節點的值(就是越上面越小)，
我們就會將其稱為最小堆積(min heap)；
反之，如果父(母)節點的值永遠大於等於子節點的值，
我們就會稱為最大堆積(max heap)。
如果上面兩個狀況都不符合的話就不是堆積囉！

也因此我們會得到一個特性：
最大堆積的最大的節點値永遠會在根節點；
最小堆積的最小的節點値永遠會在根節點。

Python中的heapq的部分呢？
它是使用串列來實作出heap的資料結構的，
且是一個最小堆積。
由於本篇以初學為導向，我們就不討論heap在二元樹上，
怎麼去處理新增/修改/刪除等操作了，
把焦點著重擺在heapq提供的可行操作上！

首先，Python可以將list輸入給heapq來排成heap的形狀，
透過heapq.heapify()函式：

>>> import heapq
>>> lt = [2,7,4,1,8,1]
>>> heapq.heapify(lt) # 直接將lt排成heap的形狀
# 在這個狀態下heap[k] <= heap[2*k+1] 且 heap[k] <= heap[2*k+2]
# 上面的k對於0或正整數均滿足(只要index存在)
>>> lt # 已經完成了，但並不是排序，所以看起來不會由小到大是正常的
[1, 1, 2, 7, 8, 4]

此外，由於現在lt已經是一個heap了，
要插入新的值或要處理其他操作的話，
要使用heapq提供的函式來處理，
常用的操作如下：
heapify (將一個list轉為heap)
heappush/heappop/heappushpop (放入/取出/先放入後取出)
nlargest/nsmallest (取前n大/前n小的元素)

當中我們只要只使用這些操作來處理，
就可以保證每次做取出(heappop)的時候，其値都會是最小的！
在這邊請留意幾點：

1. 當使用append或者del(也就是用list的方式來動到lt)時，
   會影響heap的狀態，若要復原只能重新heapify
2. 由於這個heap是min heap，
   所以nsmallest(取前n小元素)速度會比較快，較有效率，
   nlargest(取前n大元素)是較沒有效率的，
   官方會建議要這樣取不如直接先排序。
3. 對於2來說，其實也有解法，
   就是當需要用到max heap時，
   我們手動將每個元素加上一個負號代入，
   如此一來就可以將min heap當max heap來用啦！

我們拿LeetCode的1046題來當例子：
https://leetcode.com/problems/last-stone-weight/
題目大意是，
有一堆石頭，石頭重量均為正整數(阿不然是會有負的嗎？)。
每次我們拿最重的兩個石頭x, y(x <= y)相撞，
結果會有兩種：

1. x == y的時候，兩顆石頭都會毀掉消失
2. x != y的時候，只會剩下一顆石頭，重量為y - x
   撞到最後，最多只會剩下1顆石頭，請問石頭的重量是多少？
   (沒有石頭的話答案就視為0)

依照這個題目，我們會發現，
只要我們能建立一個max heap，
一切都會變得很輕鬆！
為什麼呢？
因為每次我們要拿兩個最重的相撞，
也就是每一輪要從heap當中取出兩個最大的值，
相減過後還有剩的，再放入heap中，
直到heap空掉，或者只剩1個值為止。

因此，我們可以如前面所提到的那樣，
先將石頭的重量加上負號並生成一個list，
再用heapq來對其處理。
我們直接來上程式碼，請對照註解來了解整個思路。

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        import heapq
        h = [-x for x in stones] # list comprehension
        heapq.heapify(h) # 生成最小堆積
        while len(h) > 1: # 堆積內還有超過1顆的石頭
            y = heapq.heappop(h) # 取第一顆，重量應該是-y
            x = heapq.heappop(h) # 取第二顆，重量應該是-x
            if y != x: # 兩顆沒有一起毀掉
                # 差值應該是-y+x，但為了放入heap中，要再加上一個負號
                heapq.heappush(h, y - x) # 再放入heap中
        if len(h) == 0: # 全部石頭都毀掉了，回傳0
            return 0
        else:
            return -h[0] # 回傳剩下的石頭的值，別忘了要負負得正

除了上述的需求外，
heap類型也適用於限縮個數的狀況。
比如說今天想要找一個班級的最強的前5名，
我們可以讓heap在個數尚未達到5個時使用heappush()；
而達到5個後呢？就使用heappushpop()，
先放入值，再將最弱的取出來丟掉。
所以當碰到"除了前5名以外，在座的各位都是垃圾"類型的情況，
特別適合使用heap來進行操作，可以有效降低需要保留的元素個數。

那麼，我們就明天見囉！